package com.clps.algorithm.chapter12;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 合并区间:
 * 输入一个区间集合,请将重叠的区间合并,每个区间每个区间用两个数字比较，分别表示区间的起始和结束位置。例如，
 * 输入区间[[1, 3], [4, 5], [8, 10], [2, 6], [9, 12], [15, 18]]，合并重叠的区间之后得到[[1, 6], [8, 12], [15, 18]]。
 *
 */
public class demo01 {
    public static void main(String[] args) {

    }

    public int[][] merge(int[][] intervals){
        Arrays.sort(intervals,(i1,i2)->i1[0] - i2[0]);

       List<int[]> merged = new LinkedList<>();
       int i = 0;
       while (i<intervals.length){
           int[] temp = {intervals[i][0], intervals[i][1]};
           int j = i+1;
           while (j<intervals.length && intervals[j][0] <=temp[1]){
               temp[1] = Math.max(temp[1],intervals[j][1]);
               j++;
           }
           merged.add(temp);
           i = j;
       }

       int[][] result = new int[merged.size()][];
       return  merged.toArray(result);
    }
}
